1579F - Array Stabilization (AND version) - CodeForces Solution

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;

void init_code(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif // ONLINE_JUDGE
}
 
                             // MACROS

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<int> maxheap;
typedef priority_queue<int, vector<int>, greater<int>> minheap;

#define ff first
#define ss second
#define pb push_back
#define FOR(i, a, b)  for(int i=a; i<=b; i++)
#define FORR(i, a, b)  for(int i=a; i>=b; i--)  
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define vlb(v, x) lower_bound(all(v), x)
#define vub(v, x) upper_bound(all(v), x)
#define slb(v, x) v.lower_bound(x)
#define sub(v, x) v.upper_bound(x)   
#define MOD 1000000007
#define MP make_pair

// Debugging
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define dbg(x)
#endif
    
                        // FUNCTIONS
ll lcm(ll a, ll b){ ll res = (a*b)/__gcd(a,b); return res; }
ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}

                                // PRIMARY FUNCTION
/*
 think about hashing while comparing contiguous elements...
 try to think backward.. 
 if you arent able to come up for answer, try to fix some variable, some bits, initial starting point or end point.....
 may be break a operation into two or combine two into one
*/

void solve()
{
    int n, d;
    cin >> n >> d;
    
    vector<int> a(n), dist(n, INT_MAX);
    FOR(i, 0, n - 1)    cin >> a[i];

    int g = __gcd(d, n);
    int count = n / g;

    queue<int> q;

    FOR(i, 0, n - 1){
        if(a[i] == 0){
            q.push(i);
            dist[i] = 0;
        }
    }

    int counter = 0;

    while(!q.empty()){
        counter++;
        if(counter >= count)    break;
        queue<int> q2;

        while(!q.empty()){
            int idx = q.front();
            q.pop();
            int new_idx = (idx + d) % n;

            a[new_idx] = a[new_idx] & a[idx];
            if(a[new_idx] == 0 && dist[new_idx] == INT_MAX){
                dist[new_idx] = counter;
                q2.push(new_idx);
            }
        }

        q = q2;
    }

    int ans = *max_element(all(dist));
    ans = (ans == INT_MAX)?-1:ans;

    cout << ans << "\n";
}



 // MAIN FUNCTION
    
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    init_code();

    int t = 1;
    cin>>t;
    
    while(t--){
        solve();
    }
    
    return 0;
}